1. Field of Invention
This invention relates in general to network management. More specifically, the invention relates to methods and systems for high-speed classification of a packet.
2. Description of the Background Art
Many advanced Internet services require routers to classify packets, based on a given criteria. Examples of advanced Internet services include routing, policy-based routing, load balancing, rate limiting, access-control in firewalls, virtual bandwidth allocation, service differentiation, traffic shaping, and traffic billing. Conventional packet classification requires the router to classify a packet, based on multiple fields in its header. The router classifies incoming packets into different groups and then performs appropriate actions, depending on the group the incoming packet belongs to, for each of the above services. A classifier specifies these groups. A classifier is a set of filters or a set of rule. For example, each rule in traffic billing could specify a set of source and destination addresses, and associate a corresponding action with it. Each of the rules in the classifier specifies a class for each of the packets, based on the fields of the packet header. Each class has an identifier, called a class ID, associated with it.
Advanced classification of packets can be based on class of service (COS) and quality of service (QoS). This advanced classification requires the router to classify the packets, based on multiple fields in the packet header. The packet header fields used for classification can be from layer 2, 3, 4, 5, and above. Known packet classification on multiple fields is carried out by using Access Control Lists (ACLs) An ACL comprises an ordered list of access control entries (ACEs). In an ACE, each rule defines a pattern (criterion) that is compared with packets to be classified. All ACEs have a similar structure, i.e., the packet header fields used in constructing an ACEs have fixed position and are related to each other by AND logical operator inside ACE. The absence of a field in a rule at pre-determined position can be assumed as a wildcard entry. Different packet classification algorithms, such as the Request for Comment (RFC) algorithm and the Turbo Access Control List (ACL) algorithm, make use of the structure present in the ACL rules to achieve speed and memory balance. RFC is the packet classification technique described in a publication titled, “Packet Classification on Multiple Fields,” by P. Gupta et al., Association for Computing Machinery (ACM) SIGCOMM '99 Proceedings, September 1999, Harvard University. Turbo ACL is Cisco patented packet classification technique, described in U.S. patent application Ser. No. 10/170,896 titled, “Incremental Compilation for Classification and Filtering Rules”, filed on Jun. 13, 2002.
In recent times, there has been a demand for flexible methods of defining more complex packet classification rules. The complex packet classification rule may include rules that have an undefined structure, i.e., the packet header fields used in defining the rule may not have a predetermined logical relation between them and are recognized by keywords preceding the field value. The logical relation between field values may be user configurable in undefined structure rules. However, the algorithms mentioned above, i.e., RFC and Turbo ACL algorithm cannot be used where the structure of the rules is not defined.
Although, some of the recent packet classification languages support nested rules, i.e., rules inside rules, thrice-nested rules, and so on, infinitely recursing rules are not used in packet classification. In a nested packet classification rule, the inner most rules or leaf rules are structured rules, whereas all the remaining rules, from leaf to top, are rules with undefined structure. The nested rules thus described are hereinafter referred to as meta-rules. However, the RFC and Turbo ACL algorithms mentioned above cannot be used with meta-rules.